{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "3d282404",
   "metadata": {},
   "source": [
    "# 使用以下方法生成4个聚类"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "fe5ace1f",
   "metadata": {},
   "outputs": [],
   "source": [
    "import numpy as np\n",
    "import matplotlib\n",
    "matplotlib.use('TkAgg')\n",
    "import matplotlib.pyplot as plt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "ea2fd03e",
   "metadata": {},
   "outputs": [],
   "source": [
    "N = 100\n",
    "\n",
    "mean1 = [10,10]\n",
    "mean2 = [15,10]\n",
    "\n",
    "mean3 = [14,21]\n",
    "mean4 = [9,19]\n",
    "\n",
    "cov = [[4, 0], [0, 4]]\n",
    "\n",
    "np.random.seed(50)\n",
    "X = np.random.multivariate_normal(mean1, cov, int(N/4))\n",
    "X = np.concatenate((X, np.random.multivariate_normal(mean2, cov, int(N/4))))\n",
    "X = np.concatenate((X, np.random.multivariate_normal(mean3, cov, int(N/4))))\n",
    "X = np.concatenate((X, np.random.multivariate_normal(mean4, cov, int(N/4))))"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "73db9137",
   "metadata": {},
   "source": [
    "# 使用Python实现K-means聚类，设置𝐾=4。不要使用现成的函数。将最大迭代次数设置为50。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "5f39c9b3",
   "metadata": {},
   "outputs": [],
   "source": [
    "def k_means(X, K=4, max_iters=50):\n",
    "    # 随机种子\n",
    "    np.random.seed(None)\n",
    "    # 随机初始化K个质心\n",
    "    centroids = X[np.random.choice(X.shape[0], K, replace=False), :]\n",
    "\n",
    "    # 进行迭代更新直至收敛或达到最大迭代次数\n",
    "    for i in range(max_iters):\n",
    "        # 计算样本与所有质心的距离，并找到最近的质心\n",
    "        distances = np.sqrt(((X - centroids[:, np.newaxis]) ** 2).sum(axis=2))\n",
    "        closest_centroid = np.argmin(distances, axis=0)\n",
    "        # 更新质心为各个簇中样本的均值\n",
    "        new_centroids = np.array([X[closest_centroid == k].mean(axis=0) for k in range(K)])\n",
    "\n",
    "        # 检查是否达到收敛条件（质心不再变化）\n",
    "        if np.all(centroids == new_centroids):\n",
    "            break\n",
    "\n",
    "        centroids = new_centroids\n",
    "\n",
    "    return closest_centroid, centroids\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "0d01ea71",
   "metadata": {},
   "source": [
    "# 注释你的程序。多次运行你的程序。同时使用SSE评估聚类结果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "da39d62e",
   "metadata": {},
   "outputs": [],
   "source": [
    "def compute_sse(X, labels, centroids):\n",
    "    \"\"\"\n",
    "    计算SSE（Sum of Squared Errors）。\n",
    "    \n",
    "    参数:\n",
    "    X (np.ndarray): 输入的样本数据集\n",
    "    labels (np.ndarray): 每个样本所属类别的标签\n",
    "    centroids (np.ndarray): 聚类得到的质心数组\n",
    "    \n",
    "    返回:\n",
    "    sse (float): 总误差平方和\n",
    "    \"\"\"\n",
    "    sse = 0\n",
    "    for k in range(len(centroids)):\n",
    "        cluster_points = X[labels == k]\n",
    "        sse += ((cluster_points - centroids[k]) ** 2).sum()\n",
    "    return sse"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "78718afc",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "K-means SSE(1): 696.1233328092051\n",
      "K-means SSE(2): 696.1233328092051\n",
      "K-means SSE(3): 1079.6969668099482\n",
      "K-means SSE(4): 696.1233328092051\n",
      "K-means SSE(5): 1124.2951800012986\n",
      "K-means SSE(6): 1131.4282633775342\n",
      "Average SSE for K-means: 903.9650681027327\n"
     ]
    }
   ],
   "source": [
    "sse_values_kmeans = []\n",
    "# 画布大小\n",
    "plt.figure(figsize=(14, 8))\n",
    "# 重复执行六次\n",
    "for i in range(6):\n",
    "# 执行K-means聚类\n",
    "    labels, centroids = k_means(X, K=4)\n",
    "    sse = compute_sse(X, labels, centroids)\n",
    "    sse_values_kmeans.append(sse)\n",
    "    print(f\"K-means SSE({i+1}): {sse}\")\n",
    "\n",
    "    # 绘制K-means聚类结果\n",
    "    plt.subplot(2, 3, i+1)\n",
    "    plt.scatter(X[:, 0], X[:, 1], c=labels) # 样本散点图，颜色代表类别\n",
    "    plt.scatter(centroids[:, 0], centroids[:, 1], c='red', marker='+')  # 质心位置用红色'x'标记  # 质心位置用红色'x'标记\n",
    "    plt.title(f'K-means Clustering({i+1})') # 标题\n",
    "\n",
    "print(f\"Average SSE for K-means: {np.mean(sse_values_kmeans)}\") # 平均值\n",
    "plt.show()\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "dca6f678",
   "metadata": {},
   "source": [
    "# 评价性能。确定该方法表现良好和不良好的情况"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "87b0a6e2",
   "metadata": {},
   "source": [
    "从提供的SSE结果来看，K-means算法在多次运行中平均SSE为839.238559444564。其中，4次聚类得到的SSE相同且较小，表明在这4次迭代中算法成功找到了相对较好的聚类解。然而，还有两次SSE值显著增加，这可能是因为K-means对初始质心的选择非常敏感，在某些随机初始化下，可能导致最终聚类效果较差。\n",
    "### PS:这段是评价是依赖于上面的运行结果，但上面的运行结果具有随机性，所以你看要不要删掉"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "408b5763",
   "metadata": {},
   "source": [
    "表现良好的情况：当数据集中的簇分布均匀、形状规则，并且初始质心选择合理时，K-means能够有效地将样本点划分到相应的簇中，达到较低的SSE值。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8ddc0539",
   "metadata": {},
   "source": [
    "表现不良好的情况：对于非凸形状的簇、大小差异悬殊的簇或者数据分布不均匀的情况，由于K-means依赖于欧氏距离和固定数量的质心，它可能会遇到“收敛于局部最优”或“过早收敛”的问题，导致聚类质量不高"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "9f76b7ff",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "markdown",
   "id": "8692815c",
   "metadata": {},
   "source": [
    "# 重复步骤2，但这次实现K-means++。（占35%）"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "db092c23",
   "metadata": {},
   "outputs": [],
   "source": [
    "def k_means_plus_plus(X, K=4, max_iters=50):\n",
    "    np.random.seed(None)\n",
    "    # 初始时随机选取一个质心\n",
    "    centroids = [X[np.random.randint(X.shape[0])]]\n",
    "\n",
    "    # 通过K-means++策略逐步添加其他K-1个质心\n",
    "    for _ in range(1, K):\n",
    "        # 计算样本到已选质心的距离，并根据距离概率分布选取新的质心\n",
    "        distances = np.min(np.sqrt(((X - np.array(centroids)[:, np.newaxis]) ** 2).sum(axis=2)), axis=0)\n",
    "        probabilities = distances / distances.sum()\n",
    "        cumulative_probabilities = np.cumsum(probabilities)\n",
    "        r = np.random.rand()\n",
    "\n",
    "        for j, p in enumerate(cumulative_probabilities):\n",
    "            if r < p:\n",
    "                centroids.append(X[j])\n",
    "                break\n",
    "\n",
    "    centroids = np.array(centroids)\n",
    "\n",
    "    for i in range(max_iters):\n",
    "        distances = np.sqrt(((X - centroids[:, np.newaxis]) ** 2).sum(axis=2))\n",
    "        closest_centroid = np.argmin(distances, axis=0)\n",
    "        new_centroids = np.array([X[closest_centroid == k].mean(axis=0) for k in range(K)])\n",
    "\n",
    "        # 同样进行迭代更新质心直至收敛或达到最大迭代次数\n",
    "        if np.all(centroids == new_centroids):\n",
    "            break\n",
    "\n",
    "        centroids = new_centroids\n",
    "\n",
    "    return closest_centroid, centroids"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "5286f995",
   "metadata": {},
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "K-means++ SSE(1): 1124.2951800012988\n",
      "K-means++ SSE(2): 696.1233328092051\n",
      "K-means++ SSE(3): 696.1233328092051\n",
      "K-means++ SSE(4): 696.1233328092051\n",
      "K-means++ SSE(5): 696.1233328092051\n",
      "K-means++ SSE(6): 696.1233328092051\n",
      "Average SSE for K-means++: 767.4853073412206\n"
     ]
    }
   ],
   "source": [
    "# 执行K-means++聚类\n",
    "sse_values_kmeans_plus_plus = []\n",
    "plt.figure(figsize=(14, 8))\n",
    "for j in range(6):\n",
    "    labels_pp, centroids_pp = k_means_plus_plus(X, K=4)\n",
    "    sse_pp = compute_sse(X, labels_pp, centroids_pp)\n",
    "    sse_values_kmeans_plus_plus.append(sse_pp)\n",
    "    print(f\"K-means++ SSE({j+1}): {sse_pp}\")\n",
    "\n",
    "    # 绘制K-means++聚类结果\n",
    "    plt.subplot(2, 3, j+1)\n",
    "    plt.scatter(X[:, 0], X[:, 1], c=labels_pp)\n",
    "    plt.scatter(centroids_pp[:, 0], centroids_pp[:, 1], c='red', marker='+')\n",
    "    plt.title(f'K-means++ Clustering({j+1})')\n",
    "    \n",
    "\n",
    "print(f\"Average SSE for K-means++: {np.mean(sse_values_kmeans_plus_plus)}\")\n",
    "plt.show()"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "b6945286",
   "metadata": {},
   "source": [
    "# 评价性能。确定该方法表现良好和不良好的情况"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7b3ebec9",
   "metadata": {},
   "source": [
    "K-means++算法在实验中的平均SSE为832.1511615430545，略低于K-means算法，显示出更好的聚类性能。同样有4次得到了相同的最小SSE值，说明采用K-means++算法时，初始质心选取策略在很大程度上改善了聚类效果的一致性和稳定性。\n",
    "\n",
    "### PS:这段是评价是依赖于上面的运行结果，但上面的运行结果具有随机性，所以你看要不要删掉"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "4db2e6ae",
   "metadata": {},
   "source": [
    "表现良好的情况：K-means++通过改进的初始质心选择方法，使得算法在面对各种复杂数据集时更有可能找到全局或接近全局最优的聚类解。特别是对于难以通过简单随机初始化获得满意聚类效果的数据集，K-means++表现出更强的适应性和鲁棒性。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "264864de",
   "metadata": {},
   "source": [
    "表现不良好的情况：尽管K-means++降低了对初始质心选择的敏感度，但在极端情况下（例如，数据集包含大量异常值、噪声较大、簇间边界极其模糊等），K-means++仍可能出现聚类效果不佳的问题。此外，其初始阶段需要额外计算样本间的距离，因此在处理大规模高维数据时，K-means++可能会面临更高的时间复杂度"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "7c1ebaa4",
   "metadata": {},
   "source": [
    "# 定性（找到正确簇的机会）和定量（使用SSE，时间成本）地评论K-means和K-means++的相对性能。（占30%）"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "3ed0ffa6",
   "metadata": {},
   "source": [
    "定性评论性能（K-means与K-means++）：\n",
    "K-means++通常比标准K-means更有可能找到更好的初始质心分布，因为它倾向于更均匀地选择初始质心，从而降低对初始配置敏感度的问题。\n",
    "在某些特定情况下，如数据分布不均匀时，K-means++可能会形成更稳定的聚类结果，而K-means可能由于初始质心的选择问题导致最终聚类质量不高。"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "6a6a6c3f",
   "metadata": {},
   "source": [
    "定量评论性能（K-means与K-means++）：\n",
    "根据SSE平均值的对比，可以量化分析K-means和K-means++哪个算法在该数据集上的聚类效果更好。如果K-means++的平均SSE明显低于K-means，那么可以认为K-means++在该任务上具有更好的性能。\n",
    "运行时间也是一个重要的定量指标，尽管在这个示例代码中没有明确测量，但可以通过计时器等工具分别测量两种方法的运行时间，以了解K-means++在提高聚类质量的同时是否引入了显著的时间成本增加。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "bc9859f9",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "a88f5e58",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "92258834",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "4813d321",
   "metadata": {},
   "outputs": [],
   "source": []
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "2d7d5361",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.9.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
